#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include "conio.h"

using namespace std;

class Tree
{
public:
	struct Tree_node
	{
		Tree_node(Tree_node *parent, int i_vertex, const vector<vector<int>> &arr_representation)
		{
			this->parent = parent;
			index = i_vertex+1;

			for (int i_child = 0; i_child < arr_representation[i_vertex].size(); ++i_child)
			{
				childs.push_back(new Tree_node(this, arr_representation[i_vertex][i_child]-1, arr_representation));
			}
		}

		int index;
		Tree_node *parent;
		vector<Tree_node*> childs;
	};

	Tree(const vector<vector<int>> &arr_representation)
	{
		root = new Tree_node(nullptr, 0, arr_representation);
	}

	void print_out_deep_search()
	{
		cout << "Deep search tree traversal:" << endl;
		print_out_deep_search_rec(root);
	}

	void print_out_breadth_search()
	{
		cout << "Bredth search tree traversal:" << endl;
		queue<Tree_node*> q;
		q.push(root);
		while(!q.empty())
		{
			Tree_node *cur_elem = q.front();
			q.pop();
			for (int i_child = 0; i_child < cur_elem->childs.size(); ++i_child)
			{
				q.push(cur_elem->childs[i_child]);
			}
			cout << cur_elem->index << " ";
		}
	}

	int count_n_of_removals_to_make_graph_without_intersecting_paths_rec(Tree_node *node, bool root)
	{
		int n_to_remove = node->childs.size() + !root - 2;
		n_to_remove = n_to_remove < 0 ? 0 : n_to_remove;

		for (int i_child = 0; i_child < node->childs.size(); ++i_child)
		{
			bool cur_link_is_removed= false;
			if (i_child < n_to_remove)
				cur_link_is_removed = true;

			n_to_remove += count_n_of_removals_to_make_graph_without_intersecting_paths_rec(node->childs[i_child], cur_link_is_removed);
		}

		return n_to_remove;
	}

	int count_n_of_removals_to_make_graph_without_intersecting_paths()
	{
		return count_n_of_removals_to_make_graph_without_intersecting_paths_rec(root, true);
	}

private:
	Tree_node *root;

	void print_out_deep_search_rec(Tree_node *node)
	{
		cout << node->index << " ";
		for (int i_child = 0; i_child < node->childs.size(); ++i_child)
		{
			print_out_deep_search_rec(node->childs[i_child]);
		}
	}
};

void main()
{
	int n_vertexes;
	cout << "Input number of vertexes:" << endl;
	cin >> n_vertexes;

	vector<vector<int>> tree_representation(n_vertexes);
	cout << "Input vertexes and their childrens (in each line - number of childs, their numbers):" << endl;
	for (int i_vertex = 0; i_vertex < n_vertexes; ++i_vertex)
	{
		int n_childs;
		cin >> n_childs;
		tree_representation[i_vertex].resize(n_childs);
		for (int i_child = 0; i_child < n_childs; ++i_child)
		{
			cin >> tree_representation[i_vertex][i_child];
		}
	}

	Tree t(tree_representation);
	t.print_out_deep_search();
	cout << endl;
	t.print_out_breadth_search();

	cout << endl << "Number of edges to remove from the tree to make graph without intersecting paths:" << endl;
	cout << t.count_n_of_removals_to_make_graph_without_intersecting_paths();
	_getch();
}